from collections import Counter, defaultdict


class Solution:
    def lengthAfterTransformations(self, s: str, t: int) -> int:
        x = Counter(s)
        for _ in range(t):
            nx = defaultdict(int)
            for k, v in x.items():
                v %= 1000000007
                if k == "z":
                    nx["a"] += v
                    nx["b"] += v
                else:
                    nx[chr(ord(k) + 1)] += v
            x = nx
        return sum(x.values()) % 1000000007


class Solution:
    def lengthAfterTransformations(self, s: str, t: int) -> int:
        x = [0] * 26
        for v in s:
            x[ord(v) - ord("a")] += 1
        for _ in range(t):
            nx = [0] * 26
            for i, v in enumerate(x):
                v %= 1000000007
                if i == 25:
                    nx[0] += v
                    nx[1] += v
                else:
                    nx[i + 1] += v
            x = nx
        return sum(x) % 1000000007


so = Solution()
print(so.lengthAfterTransformations(s="abcyy", t=2))
print(so.lengthAfterTransformations(s="abcyy", t=25))
